//统计所有小于非负整数 n 的质数的数量。 
//
// 示例: 
//
// 输入: 10
//输出: 4
//解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
// 
// Related Topics 哈希表 数学 
// 👍 382 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//Java：计数质数
public class P204CountPrimes{
    public static void main(String[] args) {
        Solution solution = new P204CountPrimes().new Solution();
        int  res=solution.countPrimes(10);
        System.out.println(res);
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countPrimes(int n) {
        int cnt=0;
        boolean[] prime=new boolean[n];
        Arrays.fill(prime,true);

        for(int i=2;i*i<n;i++){
            if(prime[i]){
                for(int j=2;i*j<n;j++){
                    prime[i*j]=false;
                }
            }
        }

        for(int i=2;i<n;i++){
            if(prime[i]){
                cnt++;
            }
        }

        return  cnt;
    }
    /*
    暴力破解会超时
    * */
    public boolean isPrimes(int n){
        for(int i=2;i*i<n;i++){
            if(n%i==0){
                return  false;
            }
        }

        return  true;
    }

    /*
    使用空间换取时间
    * */
    public  boolean isPrimes1(int n){
        boolean[] prime=new boolean[n];
        Arrays.fill(prime,true);

        for(int i=2;i<n;i++){
            if(prime[i]){
                for(int j=2;i*j<n;j++){
                    prime[i*j]=false;
                }
            }
        }

        return prime[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
